package datastructure.heap2;

import java.util.Arrays;

/**
 * 大顶堆
 *
 * @author 杨 强
 * @package datastructure.heap2
 * @createTime 2023-03-19 14:26
 */
public class MaxHeap {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5, 6, 7};
        MaxHeap maxHeap = new MaxHeap(array);
        System.out.println(Arrays.toString(maxHeap.array));
    }

    int[] array;
    // 元素个数
    int size;


    /**
     * 获取堆顶元素
     *
     * @return 堆顶元素
     */
    public int peek() {
        return array[0];
    }

    /**
     * 删除堆顶元素
     *
     * @return 堆顶元素
     */
    public int poll() {
        // 记录返回值
        int top = array[0];
        // 先把0位置和最后一个元素交互,这样删除不用移动数组
        swap(0, size - 1);
        size--;
        // 然后对数组进行下潜操作,也就是维护数组为大顶堆特性
        down(0);
        return top;
    }


    /**
     * 删除指定索引处元素
     *
     * @param index 索引
     * @return 被删除元素
     */
    public int poll(int index) {
        // 得到需要删除的值
        int deleted = array[index];
        // 把位置进行交换到数组最后下标,这样删除不用移动数组
        swap(index, size - 1);
        size--;
        // 下潜
        down(index);
        return deleted;
    }

    /**
     * 替换堆顶元素
     * @param replaced 新元素
     */
    public void replace(int replaced) {
        array[0] = replaced;
        down(0);
    }

    /**
     * 堆的尾部添加元素
     *
     * @param offered 新元素
     * @return 是否添加成功
     */
    public boolean offer(int offered) {
        // 判断满了没
        if (size == array.length) {
            return false;
        }
        // 元素上浮,就是可能添加的元素在最后的子节点,但是可能这个元素比父节点大
        up(offered);
        size++;
        return true;
    }

    /**
     *  将 offered 元素上浮: 直至 offered 小于父元素或到堆顶
     * @param offered
     */
    private void up(int offered) {
        // size的下标就是堆的尾部,也就是数据需要添加的下标
        int child = size;
        // 大于0就一直进行上浮操作
        while (child > 0) {
            // 得到父节点: child - 1) / 2;
            int parent = (child - 1) / 2;
            // 然后把新元素和父元素进行比较
            if (offered > array[parent]) {
                // 父节点的值放到新的子节点来
                array[child] = array[parent];
            } else {
                break;
            }
            // 新元素需要添加到的下标位置替换为父节点的下标位置
            child = parent;
        }
        // 添加元素
        array[child] = offered;
    }

    /**
     * 构造方法:初始化大顶堆并且设置容量
     * @param capacity
     */
    public MaxHeap(int capacity) {
        array = new int[capacity];
    }
    /**
     * 构造方法, 传进来一个数组,然后把数组构建为大顶堆数组
     * @param array
     */
    public MaxHeap(int[] array) {
        this.array = array;
        this.size = array.length;
        heapIfy();
    }

    /**
     * 建堆
     */
    private void heapIfy(){
        // 找到数组的最后一个非叶子节点: size / 2 - 1
        for (int i = size; i >= 0 ; i--) {
            // 然后对每个非叶子节点(非叶子节点就是父节点)进行下潜操作,就是比较父节点和子节点,进行满足大顶堆特性,父节点比子节点大
            down(i);
        }
    }

    /**
     * 将 parent 索引处的元素下潜: 与两个孩子较大者交换, 直至没孩子或孩子没它大
     * @param parent
     */
    private void down(int parent) {
        // 找到非叶子节点的左右子节点
        int left = parent * 2 + 1;
        int right = left + 1;
        // 假设父节点是最大的
        int max = parent;
        // 进行左右比较
        if (left < size && array[left] > array[max]) {
            max = left;
        }
        if (right < size && array[right] > array[max]) {
            max = right;
        }
        // 找到了更大的孩子节点,然后就进行元素替换,然后进行下一轮比较.
        if (max != parent) {
            swap(max, parent);
            down(max);
        }
    }

    /**
     * 交换两个索引处的元素
     * @param i
     * @param j
     */
    private void swap(int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}
